/*
 * Copyright (c) Scrap Material Junior Brother, Xin. 2023-2023. All rights reserved.
 */

package link;

import java.util.NoSuchElementException;

/**
 * 单链表Java实现
 *
 * @author xin
 * @since 2023-04-30
 */
public class MyLink {

    public Node head;

    private void addFirst(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            return;
        }
        node.next = head;
        head = node;
    }

    private void removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        head = head.next;
    }

    public void addLast(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    private Node prev(int index) {
        int count = 0;
        Node cur = head;
        while (count < index - 1 && cur.next != null) {
            cur = cur.next;
            count++;
        }
        if (count != index - 1) {
            throw new NoSuchElementException();
        }
        return cur;
    }

    private Integer getNode(int index) {
        int count = 0;
        Node cur = head;
        while (count < index && cur.next != null) {
            cur = cur.next;
            count++;
        }
        if (count != index) {
            throw new NoSuchElementException();
        }
        return cur.data;
    }

    private void removeLast() {
        Node node = prev(size() - 1);
        node.next = null;
    }

    private void add(int index, int data) {
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        Node node = new Node(data);
        Node prev = prev(index);
        node.next = prev.next;
        prev.next = node;
    }

    private void remove(int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            head = head.next;
            return;
        }
        Node node = prev(index);
        node.next = node.next.next;
    }

    private void removeData(int data) {
        Node cur = head;
        if (cur != null && cur.data == data) {
            head = cur.next;
        }
        while (cur != null) {
            if (cur.next != null && cur.next.data == data) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
    }

    private boolean contain(int data) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == data) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    private int size() {
        int len = 0;
        Node cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }

    private void reverse() {
        if (head == null || head.next == null) {
            return;
        }
        Node beg = null;
        Node mid = head;
        Node end = head.next;
        while (end != null) {
            mid.next = beg;
            beg = mid;
            mid = end;
            end = end.next;
        }
        mid.next = beg;
        head = mid;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        Node cur = head;
        int index = 0;
        while (cur != null) {
            sb.append("[").append(index).append("]==>").append(cur.data).append(", ");
            index++;
            cur = cur.next;
        }
        sb.append("size:").append(index).append("}");
        return sb.toString();
    }

    public static void main(String[] args) {
        MyLink myLink = new MyLink();
        System.out.println("toString:\t" + myLink);

        myLink.addFirst(1);
        System.out.println("addFirst:\t" + myLink);

        myLink.addFirst(2);
        System.out.println("addFirst:\t" + myLink);

        System.out.println("getNode: \t" + myLink.getNode(0));
        System.out.println("getNode: \t" + myLink.getNode(1));

        myLink.removeFirst();
        System.out.println("removeFirst:" + myLink);

        myLink.addLast(2);
        System.out.println("addLast:\t" + myLink);

        myLink.addLast(4);
        System.out.println("addLast:\t" + myLink);

        myLink.removeLast();
        System.out.println("removeLast: " + myLink);

        myLink.add(2, 4);
        System.out.println("add:\t" + myLink);

        myLink.add(3, 3);
        System.out.println("add:\t" + myLink);

        myLink.add(2, 3);
        System.out.println("add:\t" + myLink);

        myLink.reverse();
        System.out.println("reverse:" + myLink);

        myLink.add(2, 3);
        System.out.println("add:\t" + myLink);

        myLink.reverse();
        System.out.println("reverse:" + myLink);

        myLink.remove(2);
        System.out.println("remove:\t" + myLink);

        myLink.removeData(3);
        System.out.println("removeData:\t" + myLink);

        myLink.add(2, 3);
        System.out.println("add:\t" + myLink);

        myLink.removeData(1);
        System.out.println("removeData:\t" + myLink);

        myLink.add(0, 1);
        System.out.println("add:\t" + myLink);

        myLink.removeData(4);
        System.out.println("removeData:\t" + myLink);

        myLink.remove(0);
        System.out.println("remove:\t" + myLink);

        System.out.println("size:\t" + myLink.size());
        // myLink.add(-1, 9);
        // myLink.add(10, 9);

        System.out.println("contain 9:\t" + myLink.contain(9));
        System.out.println("contain 4:\t" + myLink.contain(4));

    }
}
